⟸ Go Back ⟸

Exercise 5 (Homework 3).

(pumping lemma)

Checking basic arithmetic is not regular

Show that the following languages over alphabet \{0,1,\#\} are not regular.

1. \{u\#v \mid u,v\in \{0,1\}^*\ \land\ v\text{ is a subword of }u\}
2. \{u\#v \mid u,v\in \{0,1\}^*\ \land\ (|u|<|v|\lor |u|\in 2\mathbb N)\}
3. \{u\#v \mid u,v\in \{0,1\}^*\ \land\ \mathtt{value}_2(u)=\mathtt{value}_2(v)\}
4. \{u\#v \mid u,v\in \{0,1\}^*\ \land\ \mathtt{value}_2(u)=\mathtt{value}_2(v)+1\}
5. \{u\#v\#z \mid u,v\in \{0,1\}^*\ \land\ \mathtt{value}_2(u)+\mathtt{value}_2(v)=\mathtt{value}_2(z)\}